package com.dh.leetcode.six;

import org.junit.Assert;
import org.junit.Test;

/**
 * @ClassName: _686_repeated_string_match
 * @Description: 686. 重复叠加字符串匹配
 * 给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
 * <p>
 * 注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。
 * <p>
 * 示例 1：
 * <p>
 * 输入：a = "abcd", b = "cdabcdab"
 * 输出：3
 * 解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。
 * 示例 2：
 * <p>
 * 输入：a = "a", b = "aa"
 * 输出：2
 * 示例 3：
 * <p>
 * 输入：a = "a", b = "a"
 * 输出：1
 * 示例 4：
 * <p>
 * 输入：a = "abc", b = "wxyz"
 * 输出：-1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/repeated-string-match
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: shouzimu
 * @Date: 2021/12/22 8:52
 */
public class _686_repeated_string_match {

    public int repeatedStringMatch(String a, String b) {
        int len = 26;
        int[] aa = new int[len];
        for (int i = 0; i < a.length(); i++) {
            aa[a.charAt(i) - 'a']++;
        }

        for (int i = 0; i < b.length(); i++) {
            if (aa[b.charAt(i) - 'a'] == 0) {
                return -1;
            }
        }
        String repeatStr = "";
        int repeat = 0;

        while (repeatStr.length() < b.length() * 3 || repeat < 3) {
            repeat++;
            repeatStr += a;
            if (repeatStr.contains(b)) {
                return repeat;
            }
        }
        return -1;
    }

    @Test
    public void repeatedStringMatchTest() {
        Assert.assertEquals(3, repeatedStringMatch("abcd", "cdabcdab"));
        Assert.assertEquals(1, repeatedStringMatch("a", "a"));
        Assert.assertEquals(2, repeatedStringMatch("a", "aa"));
        Assert.assertEquals(-1, repeatedStringMatch("abc", "xyz"));
    }
}
